|
In mathematics, a balanced matrix ''B'' is a 0-1 matrix that does not contain any square submatrix of odd order having row and column sum equal to 2. Balanced matrices are important in linear programs such as the set partitioning problem, as they are naturally integer. 0-1 Totally unimodular matrices are a subset of balanced matrices, and balanced matrices are a subset of perfect matrices, therefore any matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be totally unimodular. The following matrix is a 3 order 2-cycle forbidden submatrix: : The following matrix is a balanced matrix as it does not contain the above nor any other odd order 2-cycle submatrix: : The following matrix is a 5 order forbidden submatrix: : ==Subsequence count== An alternative method of identifying a balanced matrix that is also a zero-one matrix is through the subsequence count, where the subsequence count ''SC'' of any row s of matrix ''A'' is :SC = || If a matrix ''A'' has SC(''s'') ≤ 1 for all rows ''s'' = 1, ..., ''m'', then ''A'' has a unique subsequence, is totally unimodular〔Ryan & Falkner 1988〕 and therefore also balanced. Note that this condition is sufficient but not necessary for ''A'' to be balanced. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「balanced matrix」の詳細全文を読む スポンサード リンク
|